/* 

给你一个字符串 s，找到 s 中最长的回文子串。

 

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：

输入：s = "cbbd"
输出："bb"
示例 3：

输入：s = "a"
输出："a"
示例 4：

输入：s = "ac"
输出："a"
 

提示：

1 <= s.length <= 1000
s 仅由数字和英文字母（大写和/或小写）组成

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-palindromic-substring
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

*/

/**
 * @param {string} s
 * @return {string}
 */
// 中心扩散
var longestPalindrome = function (s) {
    const len = s.length;
    let start = 0;
    let max = 1;

    const expandAroundFromCenter = (left, right) => {
        while (left >= 0 && right <= len && s[left] === s[right]) {
            if (right - left + 1 > max) {
                max = right - left + 1;
                start = left;
            }
            left--;
            right++;
        }
    }

    for (let i = 0; i < len; i++) {
        // 以 i 为中心
        expandAroundFromCenter(i - 1, i + 1);
        // 以 i 和 i + 1 为中心
        expandAroundFromCenter(i, i + 1);
    }

    return s.substring(start, start + max);
};


// dp
// 题解：https://leetcode-cn.com/problems/longest-palindromic-substring/solution/5-zui-chang-hui-wen-zi-chuan-by-alexer-660/
var longestPalindrome = function (s) {
    const len = s.length;
    let res = '';
    // 下面初始化一个二维数组的方式值得学习
    const dp = Array.from(new Array(len), () => new Array(len).fill(0));
    for (let i = 0; i < len; i++) {
        for (let j = i; j >= 0; j--) {
            // 一定要先判断j - i < 2 再判断 dp[i + 1][j - 1]，j - i < 2：表示子串是一个长度为0或1的回文串
            dp[i][j] = s[i] === s[j] && (i - j < 2 || dp[i - 1][j + 1]);
            if (dp[i][j] && i - j + 1 > res.length) {
                res = s.substring(j, i + 1);
            }
        }
    }
    return res;
};